package Leetcode.链表;

/**
 * @ClassName 合并K个排序链表
 * @since: 2023/8/12 09:19
 * @auth: kirito
 * @description:
 **/
public class 合并K个排序链表 {
//    public static class ListNode {
//        int val;
//        ListNode next;
//        ListNode() {}
//        ListNode(int val) { this.val = val; }
//        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; i++) {
            ans = mergeTwoLists2(ans, lists[i]);
        }
        return ans;
    }
    //顺序合并  即一条一条链表合并
    /**
     * 合并两个已排序链表，返回一个新的链表。
     *
     * @param list1 第一个已排序链表的头节点
     * @param list2 第二个已排序链表的头节点
     * @return 合并后的已排序链表的头节点
     */
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        // 检查链表是否为空
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1; // 返回非空链表，如果有一个为空
        }

        // 创建新链表的头节点
        ListNode head = new ListNode(0);
        ListNode tail = head; // 用于追踪新链表的尾部
        ListNode a = list1, b = list2; // 分别追踪链表 list1 和 list2 的当前节点

        // 遍历链表 list1 和 list2，将较小的节点加入到新链表
        while (a != null && b != null) {
            if (a.val < b.val) {
                tail.next = a; // 将较小节点连接到新链表
                a = a.next; // 移动 list1 的指针到下一个节点
            } else {
                tail.next = b; // 将较小节点连接到新链表
                b = b.next; // 移动 list2 的指针到下一个节点
            }
            tail = tail.next; // 移动新链表的尾指针到刚刚添加的节点
        }

        // 将剩余的链表部分连接到新链表
        tail.next = (a != null ? a : b);

        return head.next; // 返回合并后的链表头节点
    }

}
